延續 (Day 25)

Detecting Concurrent Writes

Dynamo-style 資料庫允許多個 client 同時寫同一個 key 的資料，意味者資料的衝突勢必會發生，雖然可以提升成 Read repair (Day 24) 和 hinted handoff (Day 25) 的問題 (也就是當節點掛掉問題來處理)，但這衝突追根究底是資料在到達多個節點時的順序不同，一個簡單的例子來說如下圖：

• Node 1 接收了 A 的寫入，但沒接收到 B 的寫入需求 (可能是網路問題)。
• Node 2 先接收了 A 的寫入，然後是 B 的寫入。
• Node 3 先接收了 B 的寫入，然後是 A 的寫入。

如果我們只是簡單覆蓋資料過去，最後在取得 X 的資料時，每個節點的資料會不一致，為了資料在每個 replica 的 eventual consistency (Day 22)，你不能指望資料庫像個黑盒子般的解決衝突，現在我們就來看看這其中有什麼黑科技吧！

Last write wins (discarding concurrent writes)

最後寫的是老大！Last write wins (LWW) 這個方法就是只保留 最近 的資料，然後覆寫和捨棄舊的資料；這裡最有趣的問題是什麼是 最近 ? 你可以選一個最大的 timestamp，你也可以選一個最大的資料版本號，LWW 也是 Cassandra 唯一支援的解衝突演算法。

LWW 是以資料庫的耐用性為成本，如果我們有多個並行寫入到同一個 key，儘管符合 w 的 quorums 量 (Day 24)，但最終只會有一筆資料存活下來，其他的資料會被安靜的被幹掉。

另外如果遺失資料是不被同意的，LWW 是個很爛的解衝突方法，這時唯一的方法就只能確保每筆資料只會寫入一次，然後另資料成為不可變，Cassandra 就使用 UUID 做它的唯一 key。

The “happens-before” relationship and concurrency

首先要了解一下什麼是 happens-before relationship 和 concurrency (並發性)：

• happens-before relationship

  以下圖為例子來說明，Client B 更新資料時是依賴於 Client A 所新增的值 (value = value + 1)，換句話說 B 的操作一定比 A 之後，也可說 B 是 因果依賴 (causally dependent) 在 A 上。

  

• concurrency

  如最上面貼過的圖 5-12，Client A 和 B 的操作可視為 concurrent (並行)，因為它們倆並不知道另一個 Client 是否有針對同一個 key 做操作，也就沒有誰依賴誰的關係了。

一個操作是否在另一個操作之後 是判斷是否為並發的關鍵，所以說 2 個操作 A 和 B 只會有 3 個關係：A 在 B 之前發生、B 在 A 之前發生、或者 A 和 B 為 concurrent (並發)，所以我們會需要一個演算法來幫助我們若是 happend-before 關係我們需要覆寫舊的值，若是並行則需要解決衝突。

Capturing the happens-before relationship

我們就用一個簡單化的購物車例子 (replica 只有一份) 來說明演算法怎麼工作吧，請先看下圖：

圖 5-13 示範了 2 個 client 同時操作購物車時之間的資料依賴關係，一開始的購物車是空的，各步驟的解釋如下：

1. Client 1 新增了 milk (牛奶) 到購物車裡，這是該 key 的第一次新增，所以資料庫儲存後也指派成 version 1，然後在回覆剛剛新增的資料給 Client 端。
2. Client 2 新增了 eggs (蛋) 到購物車裡，Client 2 並不知道 Client 1 已經並行且成功的新增了 milk (牛奶) 到購物車裡，資料庫對 Client 2 的寫入指派成 version 2，然後將 eggs 和 milks 分開來存，最後在回覆這 2 個值給 Client 2。
3. Client 1 不知 Client 2 新增 eggs 成功，他這時想新增 flour (麵粉) 至購物車裡，所以 Client 1 認為此時購物車應該是 [milk, flour] ，所以就隨著先前取得的 version 1 一起傳給資料庫，跟它說我想覆寫 version 1 的資料成為 [milk, flour]，但是這裡已經有個並行寫入的 [eggs] ，因此資料庫就對 [milk, flour] 指派了個 version 3 的編號，並覆寫了 version 1 的 [milk]，同時保留 version 2 的值 [eggs]，然後把留下來的所有值回傳給 Client 1 。
4. 同時，Client 2 想新增 ham (火腿) 至購物車中，Client 2 此時並不知道 Client 1 已新增成功 flour，Client 2 先前已從資料庫接收到 2 個值 [milk] 和 [eggs]，所以 client 端可以合併他們並加入想要新增的 ham (火腿) 成為新的值 [milk, eggs, ham]，Client 2 一樣隨著前一個接收到的 version 2 編號一起將新值傳給資料庫，資料庫一樣知道 version 2 的 [eggs] 要被覆寫成新的值，但此時有並行的 version 3 [milk, flour] 存在，所以就保留 version 3，並將 [milk, eggs, ham] 指派成 version 4。
5. 最後，Client 1 想新增 bacon (培根)，一樣合併 version 3 中的資料成為 [milk. flour, eggs, bacon]，並告知資料庫要覆寫 version 3 (注意 verison 2 的 eggs 已被上一步覆寫了)，一樣因為有並行的 [eggs, milk, harm] 資料存在，所以資料庫也是持續保留這 2 個值。

圖 5-13 的資料流可以視覺化成下圖，自從另一個 Client 在做並行操作後，每一個 client 都沒有維持在最新資料，但舊的 version 資料最終還是會被覆寫成新的，且沒有資料會遺失。

這裡要留意的是寫入時務必要搭配 version 編號，否則不會覆寫任何資料。

Merging concurrently written values

這個演算法雖然可以不讓資料被捨棄，相對的它會造成 Client 額外的工作，Client 必須做合併的工作，寫入衝突在 Day 23 時有介紹過，依不同場景能選擇不同方法，最簡單的方法就是上面介紹過的 LWW；圖 5-13 的購物車例子是使用 union (聯集) 方法。

合併的工作是很複雜且容易錯誤的，需要努力為其設計資料結構執行，有興趣的可以找書看 “Automatic Conflict Resolution” on page 174 講 Riak 怎麼為其設計一個資料型態來做合併。

Version vectors

圖 5-13 介紹的例子是針對單一 replica，那本章的重點 leaderless replication 呢？

這時我們就需要每個 replica 中的每個 key 都會有自己的 version 編號，這個 version 的集合稱為 version vetor ，這個 version vector 會讓資料庫區分哪些是覆寫，哪些是並行來的資料，然後其他的處理概念跟單一 replica 差不多。

總結

終於到總結啦！

Replication 這章首先在講做分散式資料的原因：Scalability, Fault tolerance/high availability (容錯 / 高可用性), Latency 。

最後在講做 replication 的方式：

Single-leader replication (Day 21, Day 22)

Multi-leader replication (Day 23)

Leaderless replication (Day 24 ~ Day 26)

明天，就會進入了 partition 環節，如何把大的資料集切成小的。